package lcof2

// 3 0 1 4 2
// 5 6 3 2 1
// 1 2 0 1 5
// 4 1 0 1 7

// NumMatrix https://leetcode.cn/problems/O4NDxx/
type NumMatrix struct {
	preSum [][]int
}

// Constructor calculate the prefix sum of matrix.
func Constructor(matrix [][]int) NumMatrix {
	m, n := len(matrix), len(matrix[0])
	preSum := make([][]int, m+1)
	for i := range preSum {
		preSum[i] = make([]int, n+1)
	}
	// calculate (0, 0) --> (i, j) presum value
	// formula: preSum[i][j] = preSum[i-1][j] + preSum[i][j-1] + matric[i][j] - preSum[i-1][j-1]
	for i := 1; i <= m; i++ {
		for j := 1; j <= n; j++ {
			preSum[i][j] = preSum[i-1][j] + preSum[i][j-1] + matrix[i-1][j-1] - preSum[i-1][j-1]
		}
	}
	return NumMatrix{preSum: preSum}
}

func (t *NumMatrix) SumRegion(row1 int, col1 int, row2 int, col2 int) int {
	// formula: preSum[x2+1][y2+1] - preSum[x1][y2+1] - preSum[x2+1][y1] + preSum[x1][y1]
	return t.preSum[row2+1][col2+1] - t.preSum[row1][col2+1] - t.preSum[row2+1][col1] + t.preSum[row1][col1]
}

/**
 * Your NumMatrix object will be instantiated and called as such:
 * obj := Constructor(matrix);
 * param_1 := obj.SumRegion(row1,col1,row2,col2);
 */
